1. Field
This disclosure generally relates to circuit for computing circular convolution.
2. Background
Convolution is an algorithm in digital signal processing used to construct the output of a system for any arbitrary input signal by analyzing the impulse response of the system. In general, for a linear system, convolution is used to describe the relationship between the input signal, the impulse response, and the output signal. Convolution can be performed in the time domain or in the frequency domain. In the time domain, an input signal is convolved with an impulse response to yield an output signal. In the frequency domain, an input spectrum is multiplied by a frequency response of the impulse response to yield an output spectrum.
Circular convolution is useful for computing the linear convolution of an input sequence where the input data is of indefinite duration or the input sequence has a length exceeding a practical value for computation. For instance, the input signal may be streaming data or a signal in streaming mode. To perform circular convolution on input samples in streaming mode, the input samples are broken up into blocks. The result of convolving the initial samples (the impulse response width) has to be added to the convolved samples at the end of the block. That is, the convolution result of the initial samples is to be added to the convolution result of the samples at the end of the block, so called the causal part.
Circular convolution of blocks of input samples is also referred to as “Block Convolution with Overlap-Add.” For instance, block convolution is a process in which the input signal is segmented into sections of length L and is convolved with the Finite Input Response (FIR) in the time domain. The desired linear convolution result is obtained by fitting the filtered sections together, usually using either an overlap-add method or an overlap-save method.
The overlap-add method can be described as follows. First, the input signal is segmented into sections of length L, and each section is convolved with the FIR of length P. The linear convolution of one section of the input signal and the FIR will result in a sequence y[n] of length (L+P−1). When a DFT of length (L+P−1) is used to compute the convolution without time aliasing, the nonzero points in the filtered sections will overlap by (P−1) points, and these overlap points are added together to construct the output signal.
The circular convolution or the block convolution with overlap-add of a streaming input signal is not a contiguous process and requires disjoint convolution (filtering) and summation after both convolution results are obtained. The computation is therefore complex and inefficient to implement.